package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/2 17:52
 */
public class J33 {

    /** 给定一个刷组,代表一个二叉树的后序遍历, 判断它是否为搜索二叉树 */
    public static boolean verifyPostorder(int[] postorder) {
        // 判断根节点
        return recur(postorder, 0, postorder.length-1);
    }

    /** 最右边代表当前的根节点. 二分递归 */
    public static boolean recur(int[] postorder, int l, int r) {
        // base case 就剩一个节点了, 直接放回是搜索二叉树
        if( l >= r ) {
            return true;
        }
        int p = l;
        while ( postorder[p] < postorder[r] ) {
            // 划分左子树
            p++;
        }
        int m = p;
        while ( postorder[p] > postorder[r] ) {
            // 划分右子树
            p++;
        }
        // p == r . 判断在 划分左子树过程中, 和右子树过程中是否出现了非法的
        // 同时, 在递归调用左子树, 和右子树判断是否合法s
        return p==r && recur(postorder, l, m-1) && recur(postorder, m, r);
    }

}
